import java.util.*;

/**
 * @author : xwj
 * @date : 2021/9/11 21:20
 * @description : 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 *                给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 * @class : test17
 **/

public class test17 {

    //1 ms	37.1 MB
    //暴力求解：采用遍历的方式，将每个数字对应的数组求出，并做笛卡尔积
    public static List<String> letterCombinations1(String digits) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < digits.length(); i++) {
            switch (digits.charAt(i)){
                case '2':
                    if (res.size() == 0) {
                        res.add("a");
                        res.add("b");
                        res.add("c");
                    } else {
                        List<String> re = new ArrayList<>();
                        re.add("a");
                        re.add("b");
                        re.add("c");
                        res = descartes(res, re);
                    }
                    break;
                case '3':
                    if (res.size() == 0) {
                        res.add("d");
                        res.add("e");
                        res.add("f");
                    } else {
                        List<String> re = new ArrayList<>();
                        re.add("d");
                        re.add("e");
                        re.add("f");
                        res = descartes(res, re);
                    }
                    break;
                case '4':
                    if (res.size() == 0) {
                        res.add("g");
                        res.add("h");
                        res.add("i");
                    } else {
                        List<String> re = new ArrayList<>();
                        re.add("g");
                        re.add("h");
                        re.add("i");
                        res = descartes(res, re);
                    }
                    break;
                case '5':
                    if (res.size() == 0) {
                        res.add("j");
                        res.add("k");
                        res.add("l");
                    } else {
                        List<String> re = new ArrayList<>();
                        re.add("j");
                        re.add("k");
                        re.add("l");
                        res = descartes(res, re);
                    }
                    break;
                case '6':
                    if (res.size() == 0) {
                        res.add("m");
                        res.add("n");
                        res.add("o");
                    } else {
                        List<String> re = new ArrayList<>();
                        re.add("m");
                        re.add("n");
                        re.add("o");
                        res = descartes(res, re);
                    }
                    break;
                case '7':
                    if (res.size() == 0) {
                        res.add("p");
                        res.add("q");
                        res.add("r");
                        res.add("s");
                    } else {
                        List<String> re = new ArrayList<>();
                        re.add("p");
                        re.add("q");
                        re.add("r");
                        re.add("s");
                        res = descartes(res, re);
                    }
                    break;
                case '8':
                    if (res.size() == 0) {
                        res.add("t");
                        res.add("u");
                        res.add("v");
                    } else {
                        List<String> re = new ArrayList<>();
                        re.add("t");
                        re.add("u");
                        re.add("v");
                        res = descartes(res, re);
                    }
                    break;
                case '9':
                    if (res.size() == 0) {
                        res.add("w");
                        res.add("x");
                        res.add("y");
                        res.add("z");
                    } else {
                        List<String> re = new ArrayList<>();
                        re.add("w");
                        re.add("x");
                        re.add("y");
                        re.add("z");
                        res = descartes(res, re);
                    }
                    break;
            }
        }
        return res;
    }
    //求笛卡尔积
    public static List<String> descartes(List<String> l1, List<String> l2){
        List<String> res = new ArrayList<>();

        for (int i = 0; i < l1.size(); i++) {
            for (int j = 0; j < l2.size(); j++) {
                String s = l1.get(i) + l2.get(j);
                res.add(s);
            }
        }
        return res;
    }

    //5 ms	38.7 MB(效率变低)
    //递归，类似数的遍历
    public static List<String> letterCombinations2(String digits) {
        //建立数字到字符的映射
        Map<Character, char[]> map = new HashMap<>();
        map.put('2',new char[]{'a','b','c'});
        map.put('3',new char[]{'d','e','f'});
        map.put('4',new char[]{'g','h','i'});
        map.put('5',new char[]{'j','k','l'});
        map.put('6',new char[]{'m','n','o'});
        map.put('7',new char[]{'p','q','r','s'});
        map.put('8',new char[]{'t','u','v'});
        map.put('9',new char[]{'w','x','y','z'});


        //结果集
        List<String> res = new ArrayList<>();
        if (digits == "" || digits.length() == 0) {
            return res;
        }
        String s = "";
        res = func(res, s, digits, map, 0);

        return res;
    }
    //递归函数
    public static List<String> func(List<String> l, String s, String digits, Map<Character, char[]> map, int index) {
        if (index == digits.length()) {
            l.add(s);
            System.out.println(s);
        } else {
            for (int i = 0; i < map.get(digits.charAt(index)).length; i++) {
                String s1 = "";
                s1 = s + map.get(digits.charAt(index))[i];
                l = func(l, s1, digits, map, index +  1);
            }
        }
        return l;
    }

    public static void main(String[] args) {
        String digits = "7";
        for (String s: letterCombinations2(digits)) {
            System.out.printf(s+" ");
        }
    }

}
